package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-03-22 11:47
 */
public class QLint460 {
    public int[] kClosestNumbers(int[] A, int target, int k) {
        int n = A.length;
        int start = 0, end = n - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        int rclose = -1;
        if(target <= A[start]) {
            rclose = start;
        } else if (target <= A[end]) {
            rclose = end;
        } else {
            rclose = end + 1;
        }

        int lclose = rclose - 1;

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            if(isRightClose(lclose, rclose, A, target)) {
                res[i] = A[rclose];
                rclose++;
            } else {
                res[i] = A[lclose];
                lclose--;
            }
        }

        return res;
    }

    private boolean isRightClose(int lclose, int rclose, int[] A, int target) {
        if(rclose >= A.length) {
            return false;
        }

        if(lclose < 0) {
            return true;
        }

        return A[rclose] - target < target - A[lclose];
    }


}
